/*
 * 顺序表是在计算机内存中以数组的形式保存的线性表，线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素、
 * 使得线性表中在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间逻辑上的相邻关系，
 * 采用顺序存储结构的线性表通常称为顺序表。
 * 顺序表是将表中的结点依次存放在计算机内存中一组地址连续的存储单元中
 */

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int ElementType;
typedef int Position;
typedef struct LNode *List;

#define MAXSIZE 100

struct LNode {
    ElementType Data[MAXSIZE];
    Position Last;
};

/* 初始化 */
List MakeEmpty() {
    List L;

    L = (List) malloc(sizeof(struct LNode));
    L->Last = -1;

    return L;
}

#define ERROR (-1)

/* 查找 */
/* 在 L 中查找值为 X 的元素，返回其所在位置 */
Position Find(List L, ElementType X) {
    Position i = 0;

    while (i <= L->Last && L->Data[i] != X)
        i++;

    if (i > L->Last) return ERROR;  /* 如果没找到，返回错误信息 */
    else return i;  /* 找到后返回的是存储位置 */
}

/* 插入 */
/* 在 L 的指定位置 P 前插入一个新元素 X */
bool Insert(List L, ElementType X, Position P) {
    Position i;

    if (L->Last == MAXSIZE - 1) {
        /* 表空间已满，不能插入 */
        printf("表满");
        return false;
    }

    /* 检查插入位置的合法性 */
    if (P < 0 || P > L->Last + 1) {
        printf("位置不合法");
        return false;
    }
    for (i = L->Last; i >= P; i--)
        /* 将位置 P 及以后的元素顺序向后移动 */
        L->Data[i + 1] = L->Data[i];

    L->Data[P] = X;  /* 新元素插入 */
    L->Last++;  /* Last 仍指向最后元素 */
    return true;
}

/* 删除 */
/* 从 L 中删除指定位置 P 的元素 */
bool Delete(List L, Position P) {
    Position i;

    /* 检查空表及删除位置的合法性 */
    if (P < 0 || P > L->Last) {
        printf("位置%d不存在元素", P);
        return false;
    }

    for (i = P + 1; i <= L->Last; i++)
        /* 将位置 P+1 及以后的元素顺序向前移动 */
        L->Data[i - 1] = L->Data[i];

    L->Last--;  /* Last 仍指向最后元素 */
    return true;
}


int main() {
    List L = MakeEmpty();
    ElementType X = 1;
    Position P = 0;
    Insert(L, X, P);

    for (X = 2; X <= 40; X++)
        Insert(L, X, L->Last + 1);

    X = 30;
    P = Find(L, X);
    if (P == ERROR)
        printf("未找到元素%d\n", X);
    else
        printf("元素%d所在位置是%d\n", X, P);

    X = 101;
    P = Find(L, X);
    if (P == ERROR)
        printf("未找到元素%d\n", X);
    else
        printf("元素%d所在位置是%d\n", X, P);

    Delete(L, 3);
    Delete(L, 10);

    for (Position i = 0; i <= L->Last; i++)
        printf("%d ", L->Data[i]);

    return 0;
}
